/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
/* Copyright 2002-2003 by Mark Wolgemuth, All rights reserved.             */
/* Copyright 2002-2003 by Employease, Inc.  All rights reserved.           */
/*                                                                         */
/* Redistribution and use in source and binary forms, with or without      */
/* modification, are permitted provided that the following conditions      */
/* are met:                                                                */
/*                                                                         */
/*    1. Redistributions of source code must retain the above copyright    */
/* notice, this list of conditions and the following disclaimer.           */
/*    2. Redistributions in binary form must reproduce the above copyright */
/* notice, this list of conditions and the following disclaimer in the     */
/* documentation and/or other materials provided with the distribution.    */
/*                                                                         */
/* THIS SOFTWARE IS PROVIDED BY THE MOD_ATHENA PROJECT ``AS IS'' AND ANY   */
/* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE       */
/* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR      */
/* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FREEBSD PROJECT OR        */
/* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,   */
/* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,     */
/* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR      */
/* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY     */
/* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT            */
/* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE   */
/* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.    */
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */

#include "ath.h"

ath_algo_def * 
ath_algo_def_alloc(apr_pool_t *p)
{
    ath_algo_def *algo_def = (ath_algo_def *)
      apr_pcalloc(p, sizeof(ath_conf_ap));
    ASSERT(algo_def);
    ath_algo_def_format(algo_def);
    return algo_def;
}

void 
ath_algo_def_format(ath_algo_def *algo_def)
{
    int i;
    ASSERT(algo_def);
    algo_def->round_robin = 0;
    algo_def->simple = ATH_ALGO_NON;
    for (i = 0; i < ATH_ALGO_FIELDS; i++)
      {
	  algo_def->dynamic[i] = (int) NULL;
      }
    algo_def->max_excluded = 0;
}

/* populate an algo def obj from str config */
ath_algo_def * 
ath_algo_def_from_str(ath_algo_def *algo, char *str_algo)
{
    int c;
    char *algo_tok;
    char *inter;
    char *sep = "-";
    int i, type;
    ASSERT(algo);

    if (str_algo == NULL)
	return NULL;

    c = *str_algo;
    switch ((char) c)
      {
      case ATH_CASE_SPC:
	  str_algo++;
	  break;
      case ATH_ALGO_ROR: /* round robin */
	  algo->round_robin = 1;
	  algo->simple = ATH_ALGO_NON;
	  for (i = 0; i < ATH_ALGO_FIELDS; i++)
	      algo->dynamic[i] = (int) NULL;
	  break;
      case ATH_ALGO_SIM: /* simple */
	  /* move to dash */
	  while ((*str_algo != '-') && (*str_algo != (int) NULL))
	      str_algo++;
	  /* trim dash */
	  if (*str_algo++ == (int) NULL)
	      break;
	  algo->round_robin = 0;
	  algo->simple = ath_algo_str_to_type(str_algo);
	  for (i = 0; i < ATH_ALGO_FIELDS; i++)
	      algo->dynamic[i] = (int) NULL;
	  break;
      case ATH_ALGO_DYN: /* dynamic */
	  /* move past word "dynamic-" */
	  algo_tok = apr_strtok(str_algo, sep, &inter); 
	  /* get first type */
	  algo_tok = apr_strtok(NULL, sep, &inter); 
	  for (i = 0; (algo_tok != NULL); i++)
	    {
		/* break if we have receive more than makes sense = #types */
		if (i > ATH_ALGO_FIELDS - 1)
		    break;
		type = ath_algo_str_to_type(algo_tok);
		algo->dynamic[i] = type;
		algo_tok = apr_strtok(NULL, sep, &inter); 
	    }
	  algo->dynamic[i] = (int) NULL; /* terminate */
	  algo->round_robin = 0;
	  algo->simple = ATH_ALGO_NON;
	  break;
	  /* default: */
	  /* nothing */
      }  
/*     str_algo++; */
/*     if ((str_algo) && ((char) *str_algo == ATH_ALGO_MAXEX)) */
/* 	algo->max_excluded = 1; */
/*     else */
/* 	algo->max_excluded = 0; */
    return algo;
}

/* convert algo_def to readable string for output */
char * 
ath_algo_def_to_str(apr_pool_t *pool, ath_algo_def *algo)
{
    char *str_out = NULL;
    char type;
    int i;
    ASSERT(algo);

    if (algo->round_robin == 1)
	str_out = "round-robin";
    else if (algo->simple != ATH_ALGO_NON)
	str_out = apr_pstrcat(pool, "simple-", (ath_algo_type_to_str(algo->simple)), NULL);
    else if (&algo->dynamic != NULL)
      {
	  str_out = "dynamic";
	  i = 0;
	  while (algo->dynamic[i] != (int) NULL)
	    {
		type = ath_algo_str_to_type(&algo->dynamic[i]);
		str_out = apr_pstrcat(pool, str_out, "-", (ath_algo_type_to_str(type)), NULL);
		i++;
	    }
      }
    if (algo->round_robin != 1)
      {
	  /* will not add if no algo type above was set (str_out NULL terminates) */
	  if (algo->max_excluded != 0)
	      str_out = apr_pstrcat(pool, str_out, " max excluded", NULL);
      }
    return str_out;
}

/* copy one algo_def object into another algo_def object */
ath_algo_def * 
ath_algo_def_copy(ath_algo_def *algdst, const ath_algo_def *algsrc)
{
    int i = 0;
    ASSERT(algdst);
    ASSERT(algsrc);
    algdst->round_robin = algsrc->round_robin;
    algdst->simple = algsrc->simple;
    ath_shm_strncpy(algdst->dynamic, algsrc->dynamic, ATH_ALGO_FIELDS);
    algdst->max_excluded = algsrc->max_excluded;
    return algdst;
}

/* the round robin algorithm
 * gives the next available member of farm
 * will loop around to the one it started with 
 *   in case only one is up
 * if all are down it returns ATH_EOA
 */
int 
ath_algo_rr(ath_farm *farm, int *ctx)
{
    ath_phys *phys = NULL;
    int i, i_start;
    register short empty = 0;
    ASSERT(farm);
    ASSERT(ctx);

    /* start at current possition */
    i = *(ctx);
    
    /* record where we started to catch loop */
    i_start = i;
    while ((phys == NULL) && (!empty))
      {
	  i++;
	  /* skip if freed spot */
	  if (farm->member_phys_idx[i] == ATH_OPN)
	      i++;
	  /* wrap around to first idx at end of array*/
	  if ((farm->member_phys_idx[i] == ATH_EOA)
	      && (i_start != ATH_EOA))
	      i = 0;

	  phys = ath_phys_for_idx(farm->member_phys_idx[i]);

	  /* see ath_types.h: ath_phys declaration 
	   * for explanation of on vs. up 
	   */
	  if (phys != NULL) /* protect against empty farm */
	    {
		if ((phys->up != ATH_UP) 
		    || (phys->in != ATH_IN)
		    || (phys->on != ATH_ON))
		  {
		      phys = NULL;
		  }
	    }
	  if ((phys == NULL)
	      && ((i_start == ATH_EOA) /* catch totally empty farm */
		  || (i == i_start))) /* catch farm with no up members */
	    {
		i = ATH_EOA;
		empty = 1;
	    }
      }
    if (i > ATH_EOA)
	*(ctx) = i;
    return i;
}

/* the simple algorithm 
 * finds the minimally loaded member in  the specified field
 * calculated as a < b, so 0 < 11 and -3040234034 < 0.9787
 *   where a and b are floats
 * returns ATH_EOA if all are down
 */
int 
ath_algo_simple(ath_farm *farm, ath_algo_def *algo_def)
{
    ath_phys *phys;
    int i = 0;
    int idx;
    float min;
    float cur;
    int firstpass = 1;
    int chosen = ATH_EOA;
    ASSERT(farm);

    /* while there is something in the member list */
    while (farm->member_phys_idx[i] != ATH_EOA)
      {
	  /* skip if it was freed using update farm remove */
	  if (farm->member_phys_idx[i] != ATH_OPN)
	    {
		idx = farm->member_phys_idx[i];
		phys = ath_phys_for_idx(idx);
		/* continue if it is up and field is specified 
		 * possible confusion here: 
		 *   field is not specified mimics all down
		 *
		 * see ath_types.h: ath_phys declaration 
		 * for explanation of on vs. up
		 */
		if ((phys != NULL) /* protect against empty farm */
		    && ((phys->up == ATH_UP) 
			&& (phys->in == ATH_UP)
			&& (phys->on == ATH_ON)
			&& (algo_def->simple != ATH_ALGO_NON)))
		  {
		      float val;
		      val = ath_algo_val_for_type(algo_def->simple, phys);
		      if (firstpass == 1)
			{
			    min = val;
			    /* i is index into farm->member_phys_idx */
			    chosen = i;
			}
		      else if (val < min)
			{
			    min = val;
			    chosen = i;
			}		      
		      firstpass = 0;
		  }
	    }
	  i++;
      }
    return chosen;
}

/* the dynamic algorithm 
 * creates data cache of each request field for each member
 * values are normalized to between 0 and 1
 * then adds together all fields for each member
 * and selects the one with lowest aggregate load 
 * additional option AthAlgoMaxExcluded prohibits selecting
 * a member that has lowest aggregate but highest in any field
 */
int 
ath_algo_dynamic(apr_pool_t *pool, ath_farm *farm, ath_algo_def *algo_def)
{
    int idx = 0;
    int i, j;
    int firstpass;
    float *maxcache;
    int cachesize;
    int chosen_idx = ATH_EOA;
    int excluded;
    float addend;
    float load = 0;
    float minload;
    ath_phys *phys;
    ASSERT(farm);

    /* first we have to get max in each load type
     * order = NM, N = #types checked, M = #farm members
     */
    j = 0;
    cachesize = strlen(algo_def->dynamic);
    maxcache = apr_pcalloc(pool, sizeof(float[cachesize]));
    while (algo_def->dynamic[j] != (int) NULL)
      {
	  firstpass = 1;
	  i = 0;
	  while (farm->member_phys_idx[i] != ATH_EOA)
	    {
		if (farm->member_phys_idx[i] != ATH_OPN)
		  {
		      idx = farm->member_phys_idx[i];
		      phys = ath_phys_for_idx(idx);
		      /* see ath_types.h: ath_phys declaration 
		       * for explanation of on vs. up
		       */
		      if ((phys != NULL) /* protect against empty farm */
			  && ((phys->up == ATH_UP) 
			      && (phys->in == ATH_UP)
			      && (phys->on == ATH_ON)))
			{
			    float val;
			    val = ath_algo_val_for_type(algo_def->dynamic[j],
							phys);
			    if (firstpass == 1)
				maxcache[j] = val;
			    else if (val > maxcache[j])
				maxcache[j] = val;
			    firstpass = 0;
			}
		  }
		i++;
	    }
	  j++;
      }
    /* now we calculate each members evenly weighted aggregate score
     * order = MN ==> total order = 2NM
     */
    i = 0;
    firstpass = 1;
    while (farm->member_phys_idx[i] != ATH_EOA)
      {
	  if (farm->member_phys_idx[i] != ATH_OPN)
	    {
		idx = farm->member_phys_idx[i];
		phys = ath_phys_for_idx(idx);
		/* may have been offlined or downed in meantime */
		/* must check again to prevent selection */
		/* means data may now be tainted by no longer available machine */
		/* too bad */
		if ((phys != NULL) 
		    && (phys->up == ATH_UP) 
		    && (phys->in == ATH_UP)
		    && (phys->on == ATH_ON))
		  {
		      j = 0;
		      load = 0;
		      addend = 0;
		      excluded = 0;
		      while (algo_def->dynamic[j] != (int) NULL)
			{
			    /* this algo can't help much where max == 0 */
			    if (maxcache[j] != 0) 
			      {
				  float val;
				  val = 
				    ath_algo_val_for_type(algo_def->dynamic[j],
							  phys);
				  addend = val / maxcache[j];
			      }		  
			    load = load + addend;
			    /* only matters if AthAlgoMaxExcluded was set */
			    if (addend == 1) /* we must have matched max */
				excluded = 1;
			    j++;
			}
		      /* set initial min, also these way we ALWAYS return something
		       * as long as farm has any members
		       */
		      if (firstpass == 1)
			{
			    minload = load;
			    chosen_idx = i;
			}
		      /* if lowest, and if exclusion doesnt matter or not excluded if it does */
		      else if ((load < minload)
			       && ((farm->algo_def->max_excluded != 1) || (excluded != 1)))
			{
			    minload = load;
			    chosen_idx = i;
			}  
		      firstpass = 0;
		  }
	    }
	  i++;
      }
    return chosen_idx;
}

/* chose and run appropriate algorithm to get 
 * farm->member_phys_idx choice
 * passing NULL as algo_def will cause it to use 
 * farm->algo_def
 */
int 
ath_algo_get_chosen(apr_pool_t *pool, 
		    ath_farm *farm, ath_algo_def *algo_tmp, int *rrctx)
{
    int chosen_idx = ATH_EOA;
    ath_engine *engine = ath_engine_get();
    ath_algo_def *algo_def;
    ASSERT(farm);

    if (algo_tmp)
	algo_def = algo_tmp;
    else
	algo_def = farm->algo_def;

    /* round robin overrides all else */
    if (algo_def->round_robin == ATH_ON)
	chosen_idx = ath_algo_rr(farm, rrctx);
    /* nominate gives immediate response overrides others  */
    /* passed in algo blocks nominate setting */
    else if ((engine->nominate_per_update == ATH_ON) && (!algo_tmp))
	chosen_idx = farm->member_chosen_idx;
    else if (algo_def->simple != ATH_ALGO_NON)
	chosen_idx = ath_algo_simple(farm, algo_def);
    else if (algo_def->dynamic[0] != (int) NULL)
	chosen_idx = ath_algo_dynamic(pool, farm, algo_def);
    return chosen_idx;
}

/* convert str algo type to ATH_ALGO_TYPE */
char 
ath_algo_str_to_type(const char *str_algo)
{
    int c, r;
    if (str_algo != NULL)
      {
	  c = *str_algo;
	  switch ((char) c)
	    {
	    case ATH_ALGO_CPU:
		r = ATH_ALGO_CPU;
		break;
	    case ATH_ALGO_NET:
		r = ATH_ALGO_NET;
		break;
	    case ATH_ALGO_LOD:
		r = ATH_ALGO_LOD;
		break;
	    case ATH_ALGO_MEM:
		r = ATH_ALGO_MEM;
		break;
	    case ATH_ALGO_DIS:
		r = ATH_ALGO_DIS;
		break;
	    case ATH_ALGO_CU0:
		r = ATH_ALGO_CU0;
		break;
	    case ATH_ALGO_CU1:
		r = ATH_ALGO_CU1;
		break;
	    case ATH_ALGO_CU2:
		r = ATH_ALGO_CU2;
		break;
	    case ATH_ALGO_CU3:
		r = ATH_ALGO_CU3;
		break;
	    case ATH_ALGO_CU4:
		r = ATH_ALGO_CU4;
		break;
	    case ATH_ALGO_CU5:
		r = ATH_ALGO_CU5;
		break;
	    case ATH_ALGO_CU6:
		r = ATH_ALGO_CU6;
		break;
	    case ATH_ALGO_CU7:
		r = ATH_ALGO_CU7;
		break;
	    case ATH_ALGO_CU8:
		r = ATH_ALGO_CU8;
		break;
	    case ATH_ALGO_CU9:
		r = ATH_ALGO_CU9;
		break;
	    default:
		r = ATH_ALGO_NON;
	    }
	  return r;
      }
    else
	return ATH_ALGO_NON;
}

/* convert ATH_ALGO_TYPE to readable str */
char * 
ath_algo_type_to_str(char c)
{
    char *type;
    switch (c)
      {
      case ATH_ALGO_NON:
	  type = ATH_ALGO_SNON;
	  break;
      case ATH_ALGO_CPU:
	  type = ATH_ALGO_SCPU;
	  break;
      case ATH_ALGO_NET:
	  type = ATH_ALGO_SNET;
	  break;
      case ATH_ALGO_LOD:
	  type = ATH_ALGO_SLOD;
	  break;
      case ATH_ALGO_MEM:
	  type = ATH_ALGO_SMEM;
	  break;
      case ATH_ALGO_DIS:
	  type = ATH_ALGO_SDIS;
	  break;
      case ATH_ALGO_CU0:
	  type = ATH_ALGO_SCU0;
	  break;
      case ATH_ALGO_CU1:
	  type = ATH_ALGO_SCU1;
	  break;
      case ATH_ALGO_CU2:
	  type = ATH_ALGO_SCU2;
	  break;
      case ATH_ALGO_CU3:
	  type = ATH_ALGO_SCU3;
	  break;
      case ATH_ALGO_CU4:
	  type = ATH_ALGO_SCU4;
	  break;
      case ATH_ALGO_CU5:
	  type = ATH_ALGO_SCU5;
	  break;
      case ATH_ALGO_CU6:
	  type = ATH_ALGO_SCU6;
	  break;
      case ATH_ALGO_CU7:
	  type = ATH_ALGO_SCU7;
	  break;
      case ATH_ALGO_CU8:
	  type = ATH_ALGO_SCU8;
	  break;
      case ATH_ALGO_CU9:
	  type = ATH_ALGO_SCU9;
	  break;
      default:
	  type = NULL;
      }
    return type;
}

float
ath_algo_val_for_type(char c, const ath_phys *phys)
{
    float val;
    ASSERT(phys);
    switch (c)
      {
      case ATH_ALGO_CPU:
	  val = phys->cpu;
	  break;
      case ATH_ALGO_NET:
	  val = phys->net;
	  break;
      case ATH_ALGO_LOD:
	  val = phys->ld;
	  break;
      case ATH_ALGO_MEM:
	  val = phys->mem;
	  break;
      case ATH_ALGO_DIS:
	  val = phys->disk;
	  break;
      case ATH_ALGO_CU0:
	  val = phys->cus0;
	  break;
      case ATH_ALGO_CU1:
	  val = phys->cus1;
	  break;
      case ATH_ALGO_CU2:
	  val = phys->cus2;
	  break;
      case ATH_ALGO_CU3:
	  val = phys->cus3;
	  break;
      case ATH_ALGO_CU4:
	  val = phys->cus4;
	  break;
      case ATH_ALGO_CU5:
	  val = phys->cus5;
	  break;
      case ATH_ALGO_CU6:
	  val = phys->cus6;
	  break;
      case ATH_ALGO_CU7:
	  val = phys->cus7;
	  break;
      case ATH_ALGO_CU8:
	  val = phys->cus8;
	  break;
      case ATH_ALGO_CU9:
	  val = phys->cus9;
	  break;
      default:
	  val = 0;
      }
    return val;
}	  
